package com.zy.algorithm.sort;

import android.util.Log;

import com.zy.algorithm.CommonUtils;
import com.zy.algorithm.bean.QuickSortStepBean;
import com.zy.algorithm.bean.SortStepBean;
import com.zy.algorithm.curtain.IScreenBean;
import com.zy.algorithm.curtain.QuickScreenBean;
import com.zy.utils.DataBuildUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class QuickSortV2Utils {
    private static final String TAG = "QuickSortV2Utils";


    public static List<IScreenBean> quickScreenV2() {
        int[] sort = DataBuildUtils.getRandomSortArray();
        return quickScreenV2(sort);
    }

    public static List<IScreenBean> quickScreenV2(int[] sort) {
        return quickSort(sort);
    }


    private static List<IScreenBean> quickSort(int[] sort) {
        List<IScreenBean> iScreenBeans = new ArrayList<>();
        HashSet<Integer> sorted = new HashSet<>();
        //第一幕不需要动画，后面的需要
        quickSort(iScreenBeans, sorted, false, sort, 0, sort.length - 1);
        return iScreenBeans;
    }

    //[left, right]
    private static void quickSort(List<IScreenBean> iScreenBeans, HashSet<Integer> sorted, boolean needScreenAnimation, int[] sort, int left, int right) {
        if (left < right) {
            List<Integer> subSetIndexList = CommonUtils.getIndexList(left, right);
            //构建子分组数组
            int[] subset = CommonUtils.getSubsetInts(sort, subSetIndexList);

            QuickScreenBean screenBean = new QuickScreenBean();
            screenBean.setNeedScreenAnimation(needScreenAnimation);
            screenBean.setSubSetIndexList(subSetIndexList);
            screenBean.setLeft(left);
            screenBean.setRight(right);

            int[] sortStart = Arrays.copyOf(sort, sort.length);
            screenBean.setSortScreenStart(sortStart);

            int[] subsetStart = Arrays.copyOf(subset, subset.length);
            screenBean.setSubSetStart(subsetStart);
            screenBean.setSortedScreenStart(sorted);


            //将sort[low,high]划分满足上述条件的两个子表
            List<SortStepBean> sortStepBeans = new ArrayList<>();

            int subPivotPos = divide(sortStepBeans, subset, 0, subset.length - 1);//划分
            int pivotPos = subPivotPos + left;
            screenBean.setCartoonStepBeanList(sortStepBeans);
            screenBean.setSubSetEnd(Arrays.copyOf(subset, subset.length));
            //数据回设
            CommonUtils.dataSetBack(sort, subset, subSetIndexList);
            screenBean.setSortScreenEnd(Arrays.copyOf(sort, sort.length));
            sorted.add(pivotPos);


            if (left == pivotPos - 1) {
                sorted.add(left);
            }

            if (pivotPos + 1 == right) {
                sorted.add(right);
            }

            Log.d("ZYDebug", "" + Arrays.toString(screenBean.getSortScreenEnd()) + " " + Arrays.toString(screenBean.getSubSetEnd()));
            screenBean.setSortedScreenEnd(sorted);
            iScreenBeans.add(screenBean);

            quickSort(iScreenBeans, sorted, true, sort, left, pivotPos - 1);
            quickSort(iScreenBeans, sorted, true, sort, pivotPos + 1, right);
        }

    }

    //划分数组使得[left,k-1]<[k]<=[k+1,right]
    private static int divide(List<SortStepBean> sortStepBeans, int[] sort, int left, int right) {

        //选取第一个元素作为基准元素
        int pivot = sort[left];
        Log.d(TAG, "start " + Arrays.toString(sort) + " left:" + left + " right:" + right + " --> ");

        int firstIndex = left;
        int secondIndex = right;

        int opFirstIndex = firstIndex;
        int opSecondIndex = secondIndex;

        int compareSize = 0; //比较次数

        boolean compareFirstInPer = true;

        HashSet<Integer> sorted = new HashSet();

        while (opFirstIndex < opSecondIndex) {


            while (opFirstIndex < opSecondIndex) {
                int firstOpV = sort[opSecondIndex];
                boolean compareResult = firstOpV < pivot;
                //if (sort[opSecondIndex] < pivot) {

                QuickSortStepBean stepBean = new QuickSortStepBean();
                stepBean.setFirstIndex(firstIndex);
                stepBean.setSecondIndex(secondIndex);
                stepBean.setOpFirstIndex(opFirstIndex);
                stepBean.setOpSecondIndex(opSecondIndex);
                stepBean.setOpFirstV(firstOpV);
                stepBean.setOpSecondV(pivot);
                stepBean.setResult(compareResult);
                stepBean.setStepStart(Arrays.copyOf(sort, sort.length));
                stepBean.setCompareSize(++compareSize);

                stepBean.setStepStartSorted(sorted);
                stepBean.setCompareFirstInPer(compareFirstInPer);


                if (compareResult) {
                    sort[opFirstIndex] = sort[opSecondIndex];//将比基准小的元素移到左端
                    sort[opSecondIndex] = -1;

                    stepBean.setStepEndSorted(sorted);
                    stepBean.setMove(true);
                    stepBean.setMoveFirstIndex(opSecondIndex);
                    stepBean.setMoveSecondIndex(opFirstIndex);
                    stepBean.setStepEnd(Arrays.copyOf(sort, sort.length));
                    stepBean.setOpFirstIndexEnd(opFirstIndex);
                    stepBean.setOpSecondIndexEnd(opSecondIndex);
                    sortStepBeans.add(stepBean);
                    compareFirstInPer = false;
                    break;
                }
                opSecondIndex--;

                stepBean.setOpFirstIndexEnd(opFirstIndex);
                stepBean.setOpSecondIndexEnd(opSecondIndex);

                if (opFirstIndex == opSecondIndex) {
                    //基准元素归位
                    sort[opFirstIndex] = pivot;

                    stepBean.setMoveBack(true);
                    stepBean.setMoveBackIndex(opFirstIndex);
                    sorted.add(opFirstIndex);
                    stepBean.setStepEndSorted(sorted);
                    stepBean.setStepEnd(Arrays.copyOf(sort, sort.length));
                    sortStepBeans.add(stepBean);
                    compareFirstInPer = false;
                } else {
                    //比较-下标移动
                    stepBean.setStepEndSorted(sorted);
                    if (compareFirstInPer) {
                        sort[opFirstIndex] = -1;
                    }
                    stepBean.setStepEnd(Arrays.copyOf(sort, sort.length));

                    sortStepBeans.add(stepBean);
                    compareFirstInPer = false;
                }
            }


            while (opFirstIndex < opSecondIndex) {
                int firstOpV = sort[opFirstIndex];
                boolean compareResult = firstOpV > pivot;

                QuickSortStepBean stepBean = new QuickSortStepBean();
                stepBean.setFirstIndex(firstIndex);
                stepBean.setSecondIndex(secondIndex);
                stepBean.setOpFirstIndex(opFirstIndex);
                stepBean.setOpSecondIndex(opSecondIndex);
                stepBean.setOpFirstV(firstOpV);
                stepBean.setOpSecondV(pivot);
                stepBean.setResult(compareResult);
                stepBean.setStepStart(Arrays.copyOf(sort, sort.length));
                stepBean.setCompareSize(++compareSize);

                stepBean.setStepStartSorted(sorted);

                stepBean.setCompareFirstInPer(compareFirstInPer);

                //if (sort[opFirstIndex] > pivot) {
                if (compareResult) {
                    sort[opSecondIndex] = sort[opFirstIndex];//将比基准大的元素移到右端
                    sort[opFirstIndex] = -1;

                    stepBean.setStepEndSorted(sorted);
                    stepBean.setMove(true);
                    stepBean.setMoveFirstIndex(opFirstIndex);
                    stepBean.setMoveSecondIndex(opSecondIndex);
                    stepBean.setStepEnd(Arrays.copyOf(sort, sort.length));
                    stepBean.setOpFirstIndexEnd(opFirstIndex);
                    stepBean.setOpSecondIndexEnd(opSecondIndex);

                    sortStepBeans.add(stepBean);
                    compareFirstInPer = false;
                    break;
                }
                opFirstIndex++;

                stepBean.setOpFirstIndexEnd(opFirstIndex);
                stepBean.setOpSecondIndexEnd(opSecondIndex);

                if (opFirstIndex == opSecondIndex) {
                    //基准元素归位
                    sort[opFirstIndex] = pivot;

                    stepBean.setMoveBack(true);
                    stepBean.setMoveBackIndex(opFirstIndex);
                    //减去base-在子分组中
                    sorted.add(opFirstIndex);
                    stepBean.setStepEndSorted(sorted);
                    stepBean.setStepEnd(Arrays.copyOf(sort, sort.length));
                    sortStepBeans.add(stepBean);
                    compareFirstInPer = false;
                } else {
                    //比较-下标移动
                    stepBean.setStepEndSorted(sorted);
                    if (compareFirstInPer) {
                        sort[opFirstIndex] = -1;
                    }
                    stepBean.setStepEnd(Arrays.copyOf(sort, sort.length));
                    sortStepBeans.add(stepBean);
                    compareFirstInPer = false;
                }
            }
        }


        Log.d(TAG, "end " + Arrays.toString(sort) + " opFirstIndex:" + opFirstIndex + " opSecondIndex:" + opSecondIndex);
        return opFirstIndex;
    }


}
